package com.algorithm.排序.基于计数的排序;

import com.algorithm.排序.Sort;

//执行流程：依次对个位数、十位数、百位数、千位数、万位数...进行排序（从低位到高位）
//个位数、十位数、百位数的取值范围都是固定的0~9，并且计数排序适合对一定范围内的整数进行排序
// 所以可以使用计数排序对它们进行排序
public class 基数排序 extends Sort<Integer> {
    @Override
    protected void sort() {
        //找出最大值
        int max = array[0];
        for (int i = 0; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }

        //从 1 开始，依次对数组元素的个位数、十位数、百位数、千位数、万位数...进行排序
        //将divider作为条件传入到countingSort方法中中
        for (int divider = 1; divider <= max ; divider *= 10) {
            countingSort(divider);
        }
    }

    //求千位数：array[i]/1000 %10 = 0
    //求百位数：array[i]/100 %10 = 5
    //求十位数：array[i]/10 %10 = 9
    //求个位数：array[i]/1 %10 = 3

    //引入计数排序作为基数排序的底层排序方案
    //divider为进制，1 即为以array[i]的个位数为条件排序，10,100....以此类推
    protected void countingSort(int divider){
        int[] counts = new int[10];

        for (int i = 0; i < array.length; i++) {
            counts[array[i]/divider % 10] ++;
        }
        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i - 1];
        }

        int[] newArray = new int[array.length];
        for (int i = array.length - 1; i >= 0; i--) {
             newArray[--counts[array[i]/divider % 10]] = array[i];
        }

        for (int i = 0; i < newArray.length; i++) {
            array[i] = newArray[i];
        }
    }

}
